Storage access systems are designed for extracting needed information (e.g. user data files, programs, or data base records) from large volumes of stored data in response to user or application needs. Such storage access systems have a wide variety of applications including computer workstation networks, and large, high performance multiprocessor general purpose computing systems. Such storage access systems are also useful for providing high throughput inquiry-response database-systems for service control points in public communications networks, large video-text systems, directory assistance systems, and airline reservation systems.
Typically, a general purpose computer system for inquiry-response data base or other applications comprises a central processor. At the front end, the central processor interfaces with the users who generate inquiries or otherwise interact with applications being executed in the central processor. At the back end the central processor interfaces with storage devices which store the user files, programs and/or a data base containing records to be accessed in response to user requests.
Illustratively, the storage devices are magnetic disks. If a data base is stored, either on disk or in the local memory of the central processor an index may be provided so that the central processor knows where in the data base to look for particular records required to respond to particular inquiries. Similarly, directories or other tables may be provided to indicate where relevant data files or programs are stored.
The design of high performance data base or application-processing systems--i.e. those with high transaction volumes accessing very large storage volumes with stringent response time criteria--is limited by two major factors. These are processor real time and the time required for physical access to storage.
Processor real time becomes a resource limit when the central processor or other processing unit in the system cannot execute instructions rapidly enough to respond to user requests in a reasonable period of time. Processor real time is required to execute instructions for front end operations (communications with users) and back-end operators (communications with storage devices). Processor real time is also required to interpret each incoming inquiry to specify the required records, files or programs, and once the required records, files or programs have been obtained, to process the records, files or programs to determine the appropriate response.
The processor real time requirements for each inquiry-response transaction severely limits the number of inquiry-response transactions that can be handled per second using the central processor dominated application processing system architecture described above. For this type of system, transaction handling capacity may be increased by using higher performance processing elements and/or by adding processing elements in series (e.g. a front end processor) to off load the main processor and/or by adding main processors in parallel to share the processing load. Since modular, multiprocessor configurations permit the assembly of very large amounts of processing capacity to execute applications in parallel, physical access to storage and control over modifications to storage by the several parallel processing elements are often important elements in creating very high capacity inquiry-response data storage access systems or application processing systems.
With higher performance processors or with multiprocessor configurations, physical access to storage can become a system bottleneck. Illustratively, physical access to records stored on magnetic disk systems is limited by the time required for the disk head to "seek" to the desired cylinder, time for the platter to rotate to the desired position, and time to transfer the data over the channel connecting the storage device to the associated processor.
Several strategies have been devised to deal with the storage access bottleneck. One such strategy is for each processing element to maintain in its local memory all (or the most frequently accessed part) of the data base. Alternatively, each processor may maintain a different part of the data base in its local memory. This approach handles larger data bases than the previously-mentioned approach but requires the preprocessing of each incoming transaction to direct it to the responsible processing element. This may be difficult to achieve, if for example the query contents do not imply the correct partition or if the data base is large. In yet another approach, replicated disk storage devices with optimizing controllers may be used. In this approach, processing elements send inquiries to an intelligent mass storage controller which assigns the inquiries to a set of mirrored disk drives containing duplicate copies of the data base. The storage controller attempts to minimize the overall average access latency by allocating queries among the various drives to minimize seek time and waiting time for disk rotation across the set of outstanding queries. The speed and volume capacity of this approach for retrieving records are limited by the capability of the intelligent storage controller and by the number and performance of the magnetic disk drives which are attached to the controller.
In short, the foregoing approaches to increasing the capabilities of inquiry and response record handling systems invoke the use of parallel processing and/or parallel storage architectures. These prior art architectures for high performance inquiry and response data base systems have limitations. First, by adding parallelism in processing and storage to increase overall system throughput, a need may be created for a mechanism to coordinate access to and modification of multiple copies of records or other data by the various transactions running on the various processing elements. This need for concurrency control may not be severe for applications where occasional inconsistent views of the data base are tolerable, or where changes to the data base can be queued and executed in batch form to prevent inconsistencies from developing. However, for more general applications, the system overhead incurred in the software mechanisms, which guarantee that each transaction receives a "true" view of the data base and which resolve conflicting attempts to read or write database records, limits the ultimate capacity of the system architectures.
Second, some applications like 800 service in the public telephone network employ data bases with defined structures. A single key (e.g. the dialed 800 number) could be used with a memory resident index to identify the location of the relevant record in storage, avoiding the need to search the entire data base to find the relevant record. For very large data bases, or for data bases which permit access through a number of keys (e.g. by phone number, by name, by address) the memory resident indices themselves may become a significant size component of the overall data base, thus requiring multiple accesses to physical storage to finally retrieve a desired record. Additionally, if "wild card" inquiries occur, i.e. inquiries which require retrieval of records on keys for which no indices were created a priori, then every record in the data base must be retrieved and the contents examined to determine which records satisfy the request. This search process may be enormously demanding on processor real time and may also saturate the storage input output bandwidth if the records reside on disk.
In another prior art approach to record access systems, content addressable storage systems have been implemented to improve efficiency in accessing records from storage. In response to an inquiry, these systems typically read an entire disk cylinder at a time and employ "high performance processors" which examine the output data stream on the fly, identifying and moving to buffers those records whose contents match a particular record request. Some indexing is often required in these systems to identify when possible the set of cylinders likely to contain the requested records. A system of this type is available from the British computer manufacturer ICL; see e.g. "Maller V.A.J. The Content Addressable File Store-CAFS", ICL Technical Journal, Vol. 1, No. 3, November 1979. This type of system permits much shorter response time to arbitrary inquiries than do systems in which a single central processor itself must sort through and retrieve a large number of candidate records. Still, based on one directory assistance benchmark for the ICL system (17 queries/sec), for limited predictable queries, this technology is still inadequate to compete effectively with highly parallel central processor type systems which utilize indexing to enable processing elements to find particular requested records. In short, the above-described inquiry and response system architectures all have limitations on the volume of transactions which can be handled per unit of time.
Accordingly, it is an object of the present invention to provide a new architecture for an inquiry and response data storage access system, which can handle a larger volume of transactions than prior inquiry and response data storage access systems.